class Solution
{
public:
    static vector<int> _palins;
    static vector<int> setupPalins()
    {
        vector<string> mid{"", "0", "1", "2", "3", "4", "5", "6", "7", "8", "9"};
        vector<int> palins{1, 2, 3, 4, 5, 6, 7, 8, 9};
        for (int i = 1; i < 10000; ++i)
        {
            for (auto &m : mid)
            {
                string iS = to_string(i);
                string revIS = iS;
                reverse(revIS.begin(), revIS.end());
                palins.push_back(stoi(iS + m + revIS));
            }
        }
        sort(palins.begin(), palins.end());
        return palins;
    }

    long long minimumCost(vector<int> &nums)
    {
        auto &palins = _palins;
        sort(nums.begin(), nums.end());

        auto isPalin = [](int n)
        {
            string s = to_string(n);
            string revS = s;
            reverse(revS.begin(), revS.end());
            return s == revS;
        };
        vector<long long> prefixSum(nums.size() + 1);
        for (int i = 0; i < nums.size(); i++)
        {
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }
        long long result = LONG_LONG_MAX;

        int i = 0;
        int palinPos = 0;
        while (i < nums.size())
        {
            while (palinPos < palins.size() && palins[palinPos] <= nums[i])
            {
                long long preSum = prefixSum[i];
                long long sufSum = prefixSum[nums.size()] - prefixSum[i];
                long long preLen = i;
                long long sufLen = nums.size() - i;
                long long cost = sufSum - sufLen * palins[palinPos] + preLen * palins[palinPos] - preSum;
                result = min(result, cost);
                palinPos++;
            }
            ++i;
        }

        if (palinPos < palins.size())
        {
            long long cost = nums.size() * palins[palinPos] - prefixSum[nums.size()];
            result = min(result, cost);
        }

        return result;
    }
};

vector<int> Solution::_palins = Solution::setupPalins();